The accurate portrayal of images which contain multiple (more than two) gray-levels, such as photographs, with a bi-tonal imaging device which can generate only two levels (e.g. black and white), such as a dot matrix printer, can be accomplished if the imaging device produces dots which are ignored by the eye at normal viewing distance. This makes it possible to take advantage of the integrating tendencies of the eye and allow it to infer an intermediate gray-level based upon the percentage of black or white pixels over some local area of the image.
The gray-level is established for each incoming image pixel by sampling the brightness of the image pixel and representing it as a binary eight-bit number, for example. Typically, for each sampled pixel, a decision must be made, based on the gray-level, whether or not to print a dot. If the maximum gray-level of a sampled pixel is 255, one may select the gray-level 128 as the threshold for a print/no print decision. In order to reduce the apparent effects of noise, the threshold may be determined by the location of the pixel in the image in accordance with an ordered dither matrix.Various types of ordered dither matrices are well-known in the art, such as the concentrated dot matrix and the diffused dot matrix, both described in, Kawamura, "Image Processing For Halftone Reproduction", Denshi Shashin Gakkai-shi (Electrophotography), Vol. .gtoreq., No. 1, 1985, pp. 51-59. Their use in enhancing apparent image quality in the presence oF noise is well-understood and need not be described here. Another useful reference is Ulichney, Digital HalFtoning, The MIT Press, Cambridge, MA. 1987.
Quantization error limits the quality of the reproduced image. Specifically, the input pixel gray-level may exceed the print threshold where a decision to print a dot has been made, or may exceed zero while falling below the print threshold where a decision to not print has been made. The error in the former case is the amount by which the incoming pixel gray-level exceeds the black or white print value. In the latter case, the error is the difference by which the incoming pixel gray-level exceeds zero. Such errors represent incoming image information which has been essentially discarded by the simple "print/no print" decision process. This problem always exists whenever a bi-tonal system must reproduce a multiple gray-level image.
This fundamental problem has been ameliorated significantly by a technique known as error diffusion, first described by Floyd and Steinberg "An Adaptive Algorithm for Spatial Grayscale". The Proceedings of SID. Vol. 17/2 (1976). In this technique, the error generated by the print/no print decision of a given pixel, rather than being simply discarded, is used to modulate the value of the next incoming pixel gray-level. The primary advantage of this technique is its ability to infer a large number of gray-levels in the reproduced bi-tonal image. It performs especially well in the presence of edges or very fine details in the image.
An image processor which employs both an ordered dither matrix and error diffusion in combination is described in U.S. Pat. Application Serial No. 134,621 entitled "Image Processor With Error Diffusion Modulated Threshold Matrix" filed Dec. 17, 1987 by Rodney Lee Miller et al. (and referenced hereinabove). The invention described in the referenced patent application is characterized by an image quality greater than that obtained from a straightforward simplistic combination of the two processes of ordered dither and error diffusion. As described in the referenced patent application, this improvement is obtained by modifying the ordered dither matrix in such a manner as to precisely counteract the artifact-generating tendency of the error diffusion process.